//
// Created by lanlu on 2025/8/6.
//

#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 比较运算符的优先级
int compare(char c1, char c2)
{
    // 如果都是加减，或者都是乘除，优先级相等
    // 如果c1是乘除，c2是加减 则优先级高
    if ((c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-'))
    {
        return 1;
    }
    return 0;
}

// 中缀转后缀
string infixToSuffix(string infix)
{
    // 输出结果
    string result;
    // 存储运算符的栈
    stack<char> opStack;
    for (char c: infix)
    {
        // 如果是左括号 直接入栈
        // 如果是右括号 弹出栈中运算符 直到左括号
        // 如果是+-*/四种运算符 判断和栈顶运算符的优先级 如果当前运算符优先级高 则入栈 否则弹出栈中运算符 直到当前运算符优先级高
        // 如果是数字 直接输出
        switch (c)
        {
            case '(': {
                opStack.push(c);
                break;
            }
            case ')': {
                // 弹出栈中运算符 直到左括号
                while (opStack.top() != '(')
                {
                    result += opStack.top();
                    opStack.pop();
                }
                // 弹出左括号 不放入结果
                opStack.pop();
                break;
            }
            case '+':
            case '-':
            case '*':
            case '/': {
                // 如果栈为空 直接存入
                // 如果栈不为空 取栈顶运算符 和 当前运算符的优先级比较 如果当前运算符优先级高 则入栈
                // 如果栈顶运算符是左括号 直接存入
                while (!opStack.empty() && opStack.top() != '(' && compare(c, opStack.top()) == 0)
                {
                    result += opStack.top();
                    opStack.pop();
                }
                opStack.push(c);
                break;
            }
            default: {
                result += c;
            }
        }
    }

    while (!opStack.empty())
    {
        result += opStack.top();
        opStack.pop();
    }
    return result;
}

int main()
{
    cout << infixToSuffix("9+(3-1)*3+10/2") << endl;
    return 0;
}
